The present invention relates to encoding and decoding apparatuses, and an image processing apparatus using the same.
Conventionally, image data or page description language (to be abbreviated as PDL hereinafter) data transferred from a computer to an image output device such as a printer is developed for drawing in the output device. Every time the data is developed for drawing, bitmap data is sent to the printer engine section. However, when contents to be developed for drawing are complex, the drawing development speed maybe lower than the drawing speed of the engine section. In this case, bitmap data developed for drawing is temporarily stored in a memory (this memory is called a page memory). After drawing development is complete in units of pages, and the bitmap data is stored in the memory, the bitmap data is sequentially sent to the printer engine section from the top of the page.
Assume that the size of paper on which the data is printed is A3, and the resolution is 600 dpi. In this case, even when the data is binary data in which the number of bits per pixel is 1, the total bitmap data amount becomes as large as 8 MB, and the large-capacity memory increases the printer cost.
To prevent this, an arrangement as shown in FIG. 1 has been examined. Data received from a computer sequentially passes through an interface section 101 for receiving the data from the computer, a temporary buffer 102 for temporarily storing the data received from the computer, a drawing section 103 for developing the data received from the computer for drawing, a band buffer 104 for writing the data developed by the drawing section for drawing, an encoding section 105 for compression-coding the bitmap data in the band buffer, a page buffer 106 for storing the data compression-coded by the encoding section, and a decoding section 107 for decoding the encoded data in the page buffer, and is finally output to a printer engine section 108 for printing bitmap data obtained by decoding. When a plurality of band buffers 104 are used to parallelly execute development processing by the drawing section 103 and encoding processing by the encoding section 105, the processing speed can be increased.
With this arrangement, the page memory capacity decreases from 8 MB in the arrangement without compression to about xc2xd to xc2xc. Instead, the band buffer 104 must be used, and the memory capacity increases accordingly. However, when the drawing development unit (this unit is called a band) is set to be a {fraction (1/16)} to {fraction (1/20)} page, the memory capacity can be decreased in total.
As the encoding scheme of the encoding section 105, a compression scheme which guarantees a predetermined value as the lowest compression ratio for arbitrary bitmap data (text, graphic, or image data) is desired because of the strong requirement for cost reduction and the purpose of minimizing the page memory capacity. As such a compression scheme, JBIG encoding having a function of learning the two-dimensional features of bitmap data to be compressed can be used.
In JBIG encoding, learning is performed by updating the contents of a RAM for holding a predictive state. This learning (update of the contents of the RAM) occurs at an irregular timing, and the time required for encoding/decoding becomes long because of the write operation in the memory. Conversely, if learning (update of the contents of the RAM) need not be performed, the encoding/decoding time shortens. When encoded data is decoded by JBIG, the rate of data output from the decoding section 107 is not constant, so the output cannot be directly output to the printer engine section 108. To solve this, a FIFO (First In First Out) memory 109 is inserted between the decoding section 107 and the printer engine section 108. The bitmap data output from the decoding section 107 is smoothed over time and then output to the printer engine section 108.
The present inventor has proposed the following processing method in a patent filed by the present applicant previously. FIG. 3 shows the arrangement of this new proposal. The proposal contents are different from FIG. 2 in the following two points.
(1) Bitmap data decoded by the decoding section 107 is written in the band buffer 104.
(2) The bitmap data written in the band buffer 104 is output to the printer engine 108 at a predetermined timing.
The differences from FIG. 2 are a data path 301 for processing (1) and a data path 302 for processing (2).
As the difference in function, processing of smoothing the bitmap data over time is performed not by the FIFO 109 but the band buffer 104, unlike FIG. 2. In FIG. 2, the band buffer 104 operates during drawing development and encoding. In the example of FIG. 3, however, the band buffer 104 also operates during decoding.
The operation timing is shown in FIG. 4. For the descriptive convenience, bitmap data of one page is divided into six bands, and the bands are named A1, B2, A3, B4, A5, and B6 from the upper side. To increase the throughput of processing, the band buffer 104 has a double buffer structure, and the two buffers are called a buffer A and a buffer B, respectively.
Drawing development processing in the band buffers is performed in the order of A1, B2, A3, B4, A5, and B6 (a in FIG. 4). A1, A3, and A5 are developed in the buffer A, and B2, B4, and B6 are developed in the buffer B. Since development of A1 is ended before the start of development of B2, compression coding of A1 is performed in parallel to development of B2 (b in FIG. 4). Subsequently, compression coding of B2 is performed in parallel to development of A3, and finally, B6 is compression-coded. When all bitmap data of one page are compression-coded, the compressed data are decoded.
Decoding is also performed in the order of A1, B2, A3, B4, A5, and B6 (c in FIG. 4), like encoding. The bitmap data A1 of one band decoded by the decoding section 107 is written in the buffer A. Subsequently, the decoded bitmap data B2 of one band is written in the buffer B. In parallel to the write in the buffer B, the bitmap data is read out from the buffer A and sent to the printer engine section 108 (d in FIG. 4), and printing of one page is started (e in FIG. 4).
Subsequently, in parallel to the write of the decoded bitmap data A3, B2 is read out and transferred to the printer engine 108, and finally, B6 is read out and transferred to the printer engine 108. With this processing, all bitmap data of one page are sent to the printer engine 108, and print output is ended (e in FIG. 4).
FIG. 5A is a block diagram of conventional JBIG encoding and decoding apparatuses used as the encoding section 105 and decoding section 107 in FIGS. 1 to 3. The operation will be briefly described.
Referring to FIG. 5A, reference numeral 501 denotes an arithmetic operation section for performing arithmetic operation in JBIG; 502, a learning RAM for holding a predictive state; 503, an ST and MPS generation section for generating expectation data to be stored in the learning RAM 502; 504, a terminal for inputting context (CX); 505, a terminal for inputting an mode signal to exchange address signal and data signal for RAM 502 in the memory clear mode; 511, a counter for generating an address signal for the learning RAM 502 in the memory clear mode; 513, a data generation section for generating zero data to be written in the learning RAM 502 in the memory clear mode; 515, a pulse generation section for generating a write pulse to be supplied to the learning RAM 502 in the memory clear mode; and 521, 523, and 525, selectors.
Before encoding or decoding, a memory clear mode signal (High) is input to the terminal 505 to clear the learning RAM 502. When this signal goes high, the selector 521 selects the counter 511, the selector 523 selects the data generation section 513, and the selector 525 selects the pulse generation section 515. While the mode signal is at low level, the counter 511 is reset to zero. When the mode signal goes high, the counter 511 starts a count-up operation. The counter value is supplied to the address terminal of the learning RAM 502 through the selector 521 to access all addresses of the learning RAM 502. Simultaneously, zero data is supplied from the data generation section 513 to the data input terminal of the learning RAM 502 through the selector 523, and a memory write pulse signal is generated by the pulse generation section 515 and supplied with the write pulse input signal to the learning RAM 502 through the selector 525. When the learning RAM 502 is completely cleared by the above operation, the memory clear mode signal inputted from the terminal 505 goes low.
The context (CX) input from the terminal 504, data NST (NEXT STATE; the next predictive state) and NMPS (NEXT MPS; the next superior symbol) generated by the ST and MPS generation section 503, and a pulse generated by a control circuit in the arithmetic operation section 501 are input to the address terminal, data input terminal, and write pulse input terminal of the learning RAM 502, respectively. After this, the encoding or decoding operation is started.
A plurality of reference pixel data are supplied to the address terminal of the learning RAM 502 as context, and a predictive state ST and superior symbol MPS corresponding to the context are read out. These pieces of information are sent to the arithmetic operation section 501, so the arithmetic operation is performed on the basis of these pieces of information. It is determined on the basis of the calculation result whether the contents of the learning RAM 502 are to be updated. If the contents are to be updated, a memory write pulse signal is supplied to the learning RAM 502 through the selector 525. Simultaneously, the ST and MPS generation section 503 generates data NST and NMPS to be newly stored in the learning RAM 502, on the basis of the data ST and MPS.
Of the data ST and MPS output from the learning RAM 502, the predictive state ST is converted into an estimated probability value LSZ (size of an inferior symbol; estimated probability value) and used for the arithmetic operation. In this example, the predictive state ST is used for control. However, the estimated probability value LSZ itself may be stored in the learning RAM 502.
FIG. 5B shows the arrangement of the arithmetic operation section 501. This will be briefly described.
Referring to FIG. 5B, reference numeral 5001 denotes an A register representing the interval size; 5002, a C register as a code register; 5003, an estimated probability value LSZ as an estimated appearance probability converted from the predictive state ST; 5004, 1-bit information to be encoded, which corresponds to the exclusive NOR output of the pixel data (PIX) and the superior symbol (MPS); 5005, a shift amount encoding circuit for obtaining a shift amount from the value (Axe2x88x92LSZ) or LSZ; 5006, a subtraction/selector section for outputting the value (Axe2x88x92LSZ) or LSZ; 5007, an addition/selector section for outputting the value {C+(Axe2x88x92LSZ)} or LSZ; 5008, a first shifter for shifting the output from the subtraction/selector section 5006 on the basis of the shift amount output from the shift amount encoding circuit 5005; 5009, a second shifter for shifting the output from the addition/selector section 5007 on the basis of the shift amount output from the shift amount encoding circuit 5005; 5010, a terminal for outputting encoded data shifted out from the second shifter; and 5011, a terminal for outputting an update designation signal UPDATE to the ST and MPS generation section 503.
The outputs from the shift amount encoding circuit 5005, the subtraction/selector section 5006, and the addition/selector section 5007 are switched on the basis of the 1-bit encoded information (output from the exclusive NOR gate). When the 1-bit information is at xe2x80x9c1xe2x80x9d, a shift amount based on the value (Axe2x88x92LSZ) is output from the shift amount encoding circuit 5005, the value (Axe2x88x92LSZ) is output from the subtraction/selector section 5006, and the value {C+(Axe2x88x92LSZ)} is output from the addition/selector section 5007. When the 1-bit information is at xe2x80x9c0xe2x80x9d, a shift amount based on the LSZ is output from the shift amount encoding circuit 5005, the value LSZ is output from the subtraction/selector section 5006, and the value C is output from the addition/selector section 5007.
As described above, as a general arrangement, encoding of the shift amount, calculation of (Axe2x88x92LSZ), and calculation of {Cxe2x88x92(Axe2x88x92LSZ)} are sequentially performed.
FIG. 13 is a flow chart schematically showing the flow of the conventionally known encoding processing. FIG. 15 is a general flow chart of the encoding algorithm xe2x80x9cENCODExe2x80x9d. The conventional encoding operation will be described with reference to FIGS. 13 and 15.
Step 1900 represents read processing. The predictive state ST and predictive symbol MPS corresponding to the pixel to be encoded are read out from the learning RAM 502. The address input in read processing has a value generated from the reference pixel group around the pixel PIX to be encoded. The shape of the reference range is called a template. FIG. 14 shows an example of the template used for JBIG encoding. In this example, a pixel 2010 is a pixel to be encoded, and 10 pixels 2000 to 2009 correspond to the reference pixel group. Data obtained by making the colors of the 10 pixels to correspond to 10-bit binary numbers is called the context CX. For the template of 10 bits, 1,024 values from 0 to 1023 are available as the value of the context.
In estimated probability value decoding processing in step 1901, the predictive state ST read out in step 1900 is converted into the estimated probability value LSZ proportional to the inferior symbol appearance probability. Subsequently, the arithmetic operation is performed using the data PIX, MPS, and LSZ. In JBIG encoding, the estimated probability value LSZ and superior symbol MPS, which are determined in units of contexts, must be adaptively updated during the process of encoding. In step 1902, it is determined on the basis of calculation xcex1 whether this update processing need be performed. This processing corresponds to the calculation of (A=LSZ) in steps 2100, 2102, 2102a, and 2101b in FIG. 15. More specifically, update processing is executed when PIXxe2x89xa0MPX, or the calculation result of (Axe2x88x92LSZ) is smaller than 0xc3x978000. When update processing is selected, calculation xcex2 and write processing are performed in step 1903.
Step 1903 is processing to be performed when update processing is necessary. In write processing in the learning RAM 502, the next predictive state NST and next superior symbol NMPS are written in the learning RAM 502. The write address is the context of the current pixel to be processed, which has been used for read processing. Calculation xcex2 corresponds to processing in steps 2103a, 2103b, 2104a, 2104b, and 2109 in FIG. 15. Write processing corresponds to processing in steps 2105 to 2108 in FIG. 15. If update processing need not be executed, calculation xcex2 and write processing are not performed. Instead, calculation xcex3 in step 1904 is performed, and the flow advances to processing of the next pixel. Calculation xcex3 is performed when update processing is unnecessary and corresponds to processing of substituting the result of (Axe2x88x92LSZ) into the A register in steps 2101a and 2101b in FIG. 15.
As is obvious to a person skilled in the art, decoding can be performed by executing processing reverse to the above-described encoding processing while inputting encoded data to the C register, and a detailed description thereof will be omitted.
However, in the conventional encoding and decoding apparatuses, a predetermined time is required to clear the learning memory before encoding or decoding processing. When encoding or decoding is performed in units of bands, as shown in FIGS. 1 to 3, a processing time is required to clear the learning RAM in units of bands. This makes it difficult to continuously encode or decode band data and imposes limitations on an increase in processing speed.
It is an object of the present invention to provide encoding and decoding apparatuses capable of solving the above problem of the prior art and increasing the processing speed even when the learning RAM need be frequently cleared for encoding or decoding in units of bands, and an image processing apparatus using the same
In order to achieve the above object, according to the present invention, there is provided an encoding/decoding apparatus having a learning function, comprising a plurality of storage means for storing learned contents, and control means for setting one of the plurality of storage means in a learning state and the other in an initialized state and switching the state for every predetermined processing. Encoding is predictive coding complying with JBIG, and the apparatus has two learning memories as the plurality of storage means. The predetermined processing corresponds to a processing unit of an apparatus using the predictive coding apparatus.
According to the present invention, there is also provided an encoding/decoding apparatus having a learning function, comprising first storage means for storing learned contents, second storage means for dividing encoding into a plurality of sequences and storing data corresponding to a current sequence number, and control means for, when a sequence number stored in the second storage means is different from a sequence number of encoding which is progressing, inhibiting the learned contents read out from the first storage means from being used for encoding, wherein a function of initializing the learned contents of the first storage means is realized every time the sequence progresses without initializing the first storage means. The data stored in the second storage means is inverted every time the sequence progresses. The second storage means comprises a storage section for performing a read and write in units of a plurality of addresses and means for separating the readout data in units of addresses.
The encoding/decoding apparatus is applied to an image processing apparatus, and when an image of one page is to be divided into a plurality of bands and processed, switching of the state or progress of the sequence corresponds to a processing shift from a band to another band.
According to the present invention, there is also provided an image processing apparatus for dividing an image of one page into a plurality of bands, encoding each band by an encoding apparatus and storing the band, and then decoding the band by a decoding apparatus and outputting the band, wherein each of the encoding and decoding apparatuses comprises a plurality of storage means for storing learned contents, and control means for setting one of the plurality of storage means in a learning state and the other in an initialized state and switching the state for every predetermined processing.
According to the present invention, there is also provided an image processing apparatus for dividing an image of one page into a plurality of bands, encoding each band by an encoding apparatus and storing the band, and then decoding the band by a decoding apparatus and outputting the band, wherein each of the encoding and decoding apparatuses comprises first storage means for storing learned contents, second storage means for dividing encoding into a plurality of sequences and storing data corresponding to a current sequence number, and control means for, when a sequence number stored in the second storage means is different from a sequence number of encoding which is progressing, inhibiting the learned contents read out from the first storage means from being used for encoding.
According to the present invention, encoding and decoding apparatuses capable of increasing the processing speed even when a learning RAM need be frequently cleared for encoding or decoding in units of bands, and an image processing apparatus using the same can be provided.
More specifically, learning memory clear processing before JBIG encoding/decoding processing takes a predetermined time. When encoding/decoding is performed in units of bands, a processing time is required to clear the learning RAM in units of bands. Conventionally, it is hard to continuously encode/decode band data. In the present invention, as the first solution to the problem, two learning RAMs are used, and one is cleared while the other is used. As the second solution to the problem, a band sequence storage memory for storing a band sequence number for every address of the learning RAM, a counter for performing a count-up operation every time the band changes, matching detection means for detecting whether the sequence matches the counter value, and means for masking the readout contents of the learning RAM on the basis of the output from the matching detection circuit are arranged to instantaneously and apparently clear the learning RAM.
With the above arrangement, even when a processing time for clearing the learning RAM in units of bands, as in the prior art, the learning RAM can be properly cleared.
Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.